Кафедра комп’ютерних інтелектуальних систем та мереж
Курсова робота
з дисципліни
«Теорія алгоритмів»
ВСТУП
Під час розробки програмних проектів часто виникає необхідність обробки великої кількості одноманітно організованих даних. У таких випадках подібні дані зручно обробляти як єдине ціле, для чого вони представляються у вигляді масиву - іменованої послідовності даних одного типу.
У курсовій роботі розглядаються такий популярний спосіб обробки масивів як сортування. Сортування-процес перестановки елементів заданої множини в певному порядку, мета якого – полегшити наступний пошук елементів у масиві.
В даний час існує безліч алгоритмів сортування масивів, які застосовуються залежно від того які умови функціонування стоять перед розроблюваної програмою.
Алгоритм - це точно визначена (однозначна) послідовність простих (елементарних) дій, які забезпечують вирішення будь-якої задачі з деякого класу, тобто такий набір інструкцій, який можна реалізувати чисто механічно, незалежно від розумових здібностей і можливостей виконавця.
Ефективність алгоритму визначається аналізом, який повинен дати чітке уявлення, по-перше, про ємнісну і, по-друге, про часову складність процесу.
Мова йде про розміри пам'яті, в якій належить розміщувати всі дані, які беруть участь в обчислювальному процесі (до них відносяться вхідні набори, проміжна і вихідна інформація), а також фізичні ресурси, витрачені виконавцем.
У курсовій роботі представлені два методи реалізації математичних задач сортування за допомогою алгоритмів. Проведена коротка характеристика використовуваних структур даних, ефективність їх застосування у даних завданнях.
ЗМІСТ
Вступ.... 2
. Завдання до курсової роботи 4
. Загальні положення 5
2.1. Число з плаваючою точкою (комою) 7
2.2. Представлення чисел з плаваючою точкою в ЕОМ 8
2.3. Стандарт IEE-754 13
3. Складання чисел з плаваючою точкою (комою) 21
3.1. Правила виконання операції додавання 22
3.2. Склад АЛУ для операції складання чисел з плаваючою точкою 26
3.3. Алгоритм додавання чисел з плаваючою точкою 26
4. Висновок 28
Додатки 29
Список літератури 31
1.ЗАВДАННЯ ДО КУРСОВОЇ РОБОТИ
Для вибору варіанта завдання визначимо цілочислову остачу від ділення виразу Y, утвореного сумою: Х+23, де Х отримана шляхом множення останньої цифри номера групи на 100. число Х = 2*100 = 200, 23 – останні цифри у заліковій книжці (номер за списком групи) .
(Y mod 2) + 1 — алгоритми покриття; 223= 1+1=2
(Y mod 2) + 1 — алгоритми сортування. 223=1+1=2
Виходячи з цього, в якості алгоритму покриття буде виступати алгоритм A2 – побудова одного мінімального покриття, а як алгоритм сортування – С2 - простим обміном (бульбашкове сортування).
АЛГОРИТМ СОРТУВАННЯ ПРОСТИМ ОБМІНОМ (БУЛЬБАШКОВЕ СОРТУВАННЯ)
Існує безліч методів сортування. Одні з них є більш ефективними, інші - простіше для розуміння. Досить простий для розуміння є сортування методом бульбашки, який також називають методом простого обміну.
1.1.1. Постановка завдання
Завданням даної роботи є побудова алгоритму сортування масиву методом простого обміну (бульбашкового покриття). Дуже часто для зручності в обчислювальної техніки однотипні дані представляються у вигляді масивів. Масив – це об'єкт даних, в якому зберігається кілька одиниць даних, ідентифікованих за допомогою одного або декількох індексів. У простому випадку масив має постійну довжину і зберігає одиниці даних одного і того ж типу.
Кількість використаних індексів масиву може бути різним. Масиви з одним індексом називають одновимірними, з двома – двовимірними і т.д. Одновимірний масив не строго відповідає вектору в математиці, двовимірний – матриці. Найчастіше застосовуються масиви з одним або двома індексами, рідше – з трьома, ще більша кількість індексів зустрічається вкрай рідко.
Алгоритм сортування бульбашкою полягає в послідовних обходах масиву з перестановкою пар сусідніх елементів (якщо потрібно) таким чином, що на кожному обході максимальний елемент «спливає» до кінця масиву - як бульбашка в воді. Потр...
